package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/23 21:26
 **/
public class Day38_5_Num92_ReverseBetween {
    class Solution {
        // 头插法
        public ListNode reverseBetween(ListNode head, int left, int right) {
            if(head == null || head.next == null) return head;
            ListNode dummyHead = new ListNode(-1);
            ListNode pre = dummyHead;
            pre.next = head;
            // 1. 找到开始反转节点的前一个节点
            int count = left-1;
            while(count-- > 0) pre = pre.next;
            ListNode cur = pre.next;
            pre.next = null;
            // 2. 开始进行反转 头插法
            count = right-left+1;
            while(count-- > 0){
                ListNode next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
                cur = next;
            }
            // 3. 找到反转后链表最后的节点 接上 反转链表后的正常链表
            while(pre.next != null) pre = pre.next;
            pre.next = cur;
            return dummyHead.next;
        }
    }
    class Solution2 {
        // 三指针法
        public ListNode reverseBetween(ListNode head, int left, int right) {
            if(head == null || head.next == null) return head;
            ListNode dummyHead = new ListNode(-1);
            ListNode pre = dummyHead;
            pre.next = head;
            // 1. 找到开始反转节点的前一个节点
            int count = left-1;
            while(count-- > 0) pre = pre.next;
            ListNode cur = pre.next;
            // 2. 开始进行反转 三指针法（pre cur next）
            count = right-left;
            while(count-- > 0){
                ListNode next = cur.next;
                cur.next = next.next;
                next.next = pre.next;
                pre.next = next;
            }
            return dummyHead.next;
        }
    }

}